#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->data = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

//堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);

	free(hp->data);
	hp->data = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

void Swap(HeapDateType* a1, HeapDateType* a2)
{
	HeapDateType tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}

//向上调整，使之成为一个堆
void AdjustUp(HeapDateType* a, int child)
{
	assert(a);

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//子小于父就交换，使父都小于等于子，构成小堆
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的插入
void HeapPush(Heap* hp, HeapDateType x)
{
	//扩容
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HeapDateType* new = (HeapDateType*)realloc(hp->data,sizeof(HeapDateType) * newcapacity);
		if (new == NULL)
		{
			perror("HeapPush()::malloc()");
			return;
		}
		hp->data = new;
		hp->capacity = newcapacity;
	}

	hp->data[hp->size++] = x;

	//向上调整，使之成为一个堆
	AdjustUp(hp->data,hp->size - 1);
}

//向下调整
void AdjustDown(HeapDateType* a,int parent,int size)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		//假设法找儿子中较小的(大)
		if (a[child] > a[child + 1] && child + 1 < size)//只有这个条件可能会越界：a[child] > a[child + 1]
		{
			child += 1;
		}

		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);//堆不能为空

	//先交换
	Swap(&(hp->data[0]), &(hp->data[hp->size - 1]));

	//删除最后一个数据
	hp->size--;

	//向下调整，使之仍为堆
	AdjustDown(hp->data,0,hp->size-1);
}

//堆的数据个数
int GetHeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

//判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}